/**
 * // Definition for a Node.
 * function Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */

/**
 * 逐层横向遍历
 * @param {Node} root
 * @return {Node}
 */
export var connect = function (root) {
  if (root == null) return root
  let cur = root // 当前节点
  while (cur.left) {
    let tmp = cur
    // 为当前层的节点的左右节点设置next
    while (tmp) {
      tmp.left.next = tmp.right
      if (tmp.next) {
        tmp.right.next = tmp.next.left
      }
      // 进入当前层的下一个节点
      tmp = tmp.next
    }
    // 进入下一层
    cur = cur.left
  }
  return root
}

/**
 * 深度优先遍历
 * @param {Node} root
 * @return {Node}
 */
export var connect2 = function (root) {
  function dfs(node) {
    if (node == null) return
    let left = node.left
    let right = node.right
    while (left) {
      left.next = right
      left = left.right
      right = right.left
    }
    dfs(node.left)
    dfs(node.right)
  }
  dfs(root)
  return root
}
